package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-12 22:22
 */
public class fib {
    public static void main(String[] args) {
        System.out.println(fib(3));
    }
    /**
     * 五部曲：1.每个数组的下标代表的是第几个fib数，fib[i]代表每个fib数的值2.地推公式：fib[n]=fib[n-1]+fib[n-2];
     * 3.dp数组的初始化dp[0]=0,dp[1]=1  4.遍历顺序：从前往后遍历
     * @param n
     * @return
     */
    public static int fib(int n){
        int[]fib=new int[n+1];
        fib[0]=1;
        fib[1]=1;
        for(int i=2;i<=n;++i){
            fib[i]=fib[i-1]+fib[i-2];
        }

        return fib[n];
    }
}
